A flash memory is a type of non-volatile memory arrays with advantages of low power consumption and small size. Therefore, flash memories are widely used in various applications, especially in portable electronic devices.
The flash memory is not overwritable. Once a portion of the flash memory is written with data, the existing data must be deleted (i.e. erased) first, then the portion can be rewritten with new data. The flash memory is composed of transistor cells. Those transistor cells are grouped into erasable blocks. The cells of one block are erasable at one time. That is, the block is a unit of data erase for the flash memory. Each block is further divided into multiple pages. The page is a unit of data programming. Typically, each page is used to store one sector of user data. However, it is possible that one page stores a portion of one sector or several sectors of user data. The sector is a unit of data transfer.
FIG. 1 is a schematic illustration showing an example of a data structure for a page 100 of the flash memory. As shown, the page 100 has a data region 110 and a spare region 120. The data region 110 is typically used for storing user data. The spare region 120 is used to store some control data such as a logical address, which is referred to as LBA 122, and a time stamp 124 for recording the time when the data is written to the data region 110, for example. The spare region 120 can also contain other information such as an error correction code (ECC).
As mentioned, the unit for programming data is a page, while the unit for erasing data is a block. When the data of a logical page, which is originally stored in a physical page, is to be updated, a usual method is to find another physical page and write new data into the new physical page. The mapping relationships between the logical page and the original and new physical pages are both recorded. FIG. 2 shows a schematic illustration of a pointer table 200. The pointer table 200 records the mapping relationships between respective logical addresses and corresponding physical addresses of the flash memory with pointers. The logical addresses can be identified by an operating system (e.g. Windows) of a computer, and the physical addresses represent the specific positions in the flash memory. For example, a first pointer 201 indicates that a logical address LBA1 corresponds to a physical address PA1, and a second pointer 202 indicates that a logical address LBA2 corresponds to a physical address PA2. That is, the data of the logical address LBA1 is stored in a position in the flash memory denoted by the physical address PA1, and the data of the logical address LBA2 is stored in a position in the flash memory denoted by the physical address PA2. When the data of the physical address PA1 corresponding to the logical address LBA1 is updated, the new data is written to a new physical address PA3, for example. Then, an additional pointer (not shown) indicating a new mapping relationship between the logical address LBA1 and the physical address PA3 will also be recorded in the pointer table 200. As can be understood, the point table 200 is of a great size since all mapping relationships for the respective logical addresses are recorded therein. For example, if the logical address LBA1 is rewritten 100 times, the mapping relationship will be updated 100 times. Accordingly, 100 pointers recording the mapping relationships between the logical address and the 100 different physical addresses will be recorded in the pointer table 200. The pointer table 200 is usually stored in a specific area of the flash memory.
When a system using the flash memory is activated, the pointer table 200 is read and written to a volatile memory such as a dynamic random access memory (DRAM) or static random access memory (SRAM). By scanning the pointer table 200, it can be known that which one of the positions of the flash memory stores the user data of a specific logical address. For example, the memory position storing the latest data for a specific logical address can be known by checking the time stamps if there are a plurality of records of this specific logical address.
When segments of the user data are updated, the pointer table 200 also needs to be updated. However, the point table is very huge if the flash memory is a high capacity memory array (e.g. 1 tera bytes). It will take a very long period of time to update the point table 200. Accordingly, the efficiency of the whole system will be degraded if the point table 200 stored in the flash memory is updated whenever any data segment is updated.